//
// Created by zhou on 2023/6/6.
// 关键路径
#include "stdlib.h"
#include "stdio.h"


#define MAXVEX 20
#define ERROR 0
#define OK 1

// 边表节点
typedef struct EdgeNode{
    // 邻接点域，存储该顶点对应的下标
    int adjvex;
    // 权值
    int weight;
    // 链域，指向下一个邻接点
    struct EdgeNode *next;
}EdgeNode;

// 顶点表结点
typedef struct VertexNode{
    // 入度
    int in;
    // 顶点信息
    int data;
    // 边表头指针
    struct EdgeNode *firstEdge;
}VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    int numNodes, numEdges;
}graphAdjList, *GraphAdjList;

// 顶点事件最早和最晚发生时间数组
int *etv, *ltv;
// 拓扑序列栈
int *stack2;
// 遍历拓扑序列栈指针
int top2;

int TopologicalSort(GraphAdjList GL) {
    // 用于遍历邻接表的指针
    EdgeNode *e;
    int i,k,gettop;
    // 栈指针域下标
    int top = 0;
    // 统计输出的顶点个数
    int count = 0;
    // 建栈用于将入度为0的顶点入栈
    int *stack;
    // 分配栈空间
    stack = (int *)malloc(GL->numNodes * sizeof (int));
    // 遍历所有顶点，将顶点入度为0的入栈
    for(i = 0; i < GL->numNodes; i++) {
        if(0 == GL->adjList[i].in) {
            stack[++top] = i;
        }
    }
    // 初始化
    top2 = 0;
    etv = (int *) malloc(GL->numNodes * sizeof(int));
    for(i = 0; i < GL->numNodes; i++) {
        etv[i] = 0;
    }
    stack2 = (int*)malloc(GL->numNodes * sizeof (int));
    // 出栈
    while (top != 0) {
        gettop = stack[top--];
        count++;
        // 拓扑序列入栈
        stack2[top2++] = gettop;
        // 遍历此顶点的所有邻接点
        for (e = GL->adjList[gettop].firstEdge; e; e = e->next) {
            // 将这些邻接点的入度减1（实际上就是断掉边）
            k = e->adjvex;
            // 若入度减少后刚好为0，则再将该顶点入栈
            if(!(--GL->adjList[k].in)) {
                stack[++top] = k;
            }
            // 从前往后找较大值
            if((etv[gettop] + e->weight) > etv[k]) {
                etv[k] = etv[gettop] + e->weight;
            }
        }
    }
    // 输出顶点数与总顶点数不一致，说明有环
    if(count < GL->numNodes) return ERROR;
    else return OK;
}

/**
 * 求关键路径
 * @param GL
 */
void CriticalPath(GraphAdjList GL) {
    EdgeNode *e;
    int i, gettop, k, j;
    // 边活动的最早和最迟发生时间
    int ete, lte;
    // 利用拓扑序列求出数组etv和拓扑排序后的栈
    TopologicalSort(GL);
    // 初始化，分配内存给顶点事件最迟发生时间数组
    ltv = (int*)malloc(GL->numNodes * sizeof (int));
    for(i = 0; i < GL->numNodes; i++) {
        // 初始化，最迟事件发生时间数组初始默认值均为最早事件发生时间数组中的最后一个值
        ltv[i] = etv[GL->numNodes - 1];
    }
    while (top2 != 0) {
        gettop = stack2[top2--];
        for (e = GL->adjList[gettop].firstEdge; e; e = e->next) {
            k = e->adjvex;
            // 求各顶点事件最晚发生时间ltv（从后往前找较小值）
            if(ltv[k] - e->weight < ltv[gettop]) {
                ltv[gettop] = ltv[k] - e->weight;
            }
        }
    }
    // 求 ete,lte,和关键路径
    for(j = 0; j < GL->numNodes; j++) {
        k = e->adjvex;
        // 活动最早发生时间 = 弧头顶点的最早事件发生时间
        ete = etv[j];
        // 活动最迟发生时间 = 弧尾顶点的最迟事件发生时间 - 边上的权值
        lte = ltv[k] - e->weight;
        // 若两者相等则在关键路径上
        if(ete == lte) {
            printf("<v%d - v%d> length: %d\n",
                   GL->adjList[j].data, GL->adjList[k].data, e->weight);
        }
    }
}